#include "../8.3.1.Adjacency matrix/ljjz.c"

typedef struct edgedata
{
    int begin, end;
    int length;
} edge;

/**
 * prim算法求最小生成树
 * @param {MGraph}          g               图的邻接矩阵存储结构
 * @param {tree}            tree            边向量
 * @return void
 */
void prim(Mgraph g, edge tree[M - 1])
{
    edge x;
    int d, min, j, k, s, v;

    for (v = 1; v < g.n; v++)
    {
        tree[v - 1].begin = 0;
        tree[v - 1].end = v;
        tree[v - 1].length = g.edges[0][v];
    }

    for (k = 0; k <= g.n - 3; k++)
    {
        min = tree[k].length;
        s = k;
        for (j = k + 1; j <= g.n - 2; j++)
        {
            if (tree[j].length < min)
            {
                min = tree[j].length;
                s = j;
            }
        }

        v = tree[s].end;
        x = tree[s];
        tree[s] = tree[k];

        for (j = k + 1; j <= g.n - 2; j++)
        {
            d = g.edges[v][tree[j].end];
            if (d < tree[j].length)
            {
                tree[j].length = d;
            }
        }
    }

    printf("最小生成树的边为：\n");
    for (k = 0; k <= g.n - 2; k++)
    {
        printf("\n %c --- %c \n", g.vexs[tree[k].begin], g.vexs[tree[k].end]);
    }
    printf("The root of it is %c\n", g.vexs[0]);
}

int main(){
    Mgraph g;
    edge tree[M - 1];
    char filename[20];
    printf("请输入文件名：");
    gets(filename);
    creat(&g, filename,0);
    prim(g, tree);
    return 0;
}